/*https://leetcode.cn/problems/count-number-of-ways-to-place-houses/submissions/562790181/
统计放置房子的方式数
24/9/7
*/


#include <iostream>

class Solution {
public:
    int Mod = 1000000007; // 模数，用于防止溢出

    int countHousePlacements(int n) {
        // 问题可以转化为在一侧放置房屋，最后结果是两侧的乘积
        // 用动态规划的思想来解决这个问题

        // dp[i][0] 表示在第 i 个位置不放置房屋的方案数
        // dp[i][1] 表示在第 i 个位置放置房屋的方案数

        // 初始化
        long long noHouse = 1; // 在第一个位置不放置房屋的方案数
        long long hasHouse = 1; // 在第一个位置放置房屋的方案数

        // 动态规划计算
        for (int i = 2; i <= n; i++) {
            long long newNoHouse = (noHouse + hasHouse) % Mod; // 当前位置不放置房屋，可以从上一个位置放或不放转移过来
            long long newHasHouse = noHouse; // 当前位置放置房屋，上一个位置必须不放

            // 更新状态
            noHouse = newNoHouse;
            hasHouse = newHasHouse;
        }

        // 最终结果是两侧的乘积
        long long totalWays = (noHouse + hasHouse) % Mod; // 一侧的总方案数
        long long ans = (totalWays * totalWays) % Mod; // 两侧的总方案数

        return ans;
    }
};